#include <stdio.h>
#include <stdlib.h>

typedef struct LNode
{
    int data;
    LNode *next;
} LNode, *LinkedList;

bool InitList(LinkedList &L);                  // 初始化
void ClearList(LinkedList &L);                 // 销毁
bool ListEmpty(LinkedList L);                  // 判空
int ListLength(LinkedList L);                  // 长度
LNode *GetElem(LinkedList L, int i);           // 按位查找
LNode *LocateElem(LinkedList L, int e);        // 按值查找
bool ListInsert(LinkedList &L, int i, int e);  // 插入
bool ListDelete(LinkedList &L, int i, int &e); // 删除
bool PrintList(LinkedList L);                  // 输出

// 初始化
bool InitList(LinkedList &L)
{
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL)
        return false;
    L->next = NULL;
    return true;
}

// 销毁
void ClearList(LinkedList &L)
{
    LNode *p;
    while (L)
    {
        p = L->next;
        free(L);
        L = p;
    }
}

// 判断是否为空
bool ListEmpty(LinkedList L)
{
    return (L->next == NULL);
}

// 求表长
int ListLength(LinkedList L)
{
    int len = 0;
    LNode *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}

// 按位查找
LNode *GetElem(LinkedList L, int i)
{
    if (i < 0)
        return NULL;
    LNode *p = L;
    int j = 0;
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}

//按值查找
LNode *LocateElem(LinkedList L, int e)
{
    LNode *p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    return p;
}

// 前插操作
bool InsertPriorNode(LNode *p, LNode *s)
{
    if (p == NULL || s == NULL)
        return false;
    s->next = p->next;
    p->next = s;
    int temp = p->data;
    p->data = s->data;
    s->data = temp;
    return true;
}

// 后插操作
bool InsertNextNode(LNode *p, int e)
{
    if (p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL)
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 插入
bool ListInsert(LinkedList &L, int i, int e)
{
    if (i < 1)
        return false;
    LNode *p = GetElem(L, i - 1);
    return InsertNextNode(p, e);
}

// 尾插法
bool ListAppend(LinkedList &L, int e) {
    LNode *ptr = L;
    while (ptr->next != NULL)
        ptr = ptr->next;
    
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL)
        return false;
    s->data = e;
    s->next = NULL;
    ptr->next = s;
    return true;
}

// 删除
bool ListDelete(LinkedList &L, int i, int &e)
{
    if (i < 1)
        return false;
    LNode *p = GetElem(L, i - 1);
    if (p == NULL)
        return false;
    if (p->next == NULL)
        return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

// 输出
bool PrintList(LinkedList L)
{
    LNode *p = L->next;
    if (!p)
        return false;
    printf("head->");
    while (p != NULL)
    {
        printf("%d->", p->data);
        p = p->next;
    }
    printf("NULL\n");
    return true;
}

bool PrintListWithoutHead(LinkedList L) {
    LNode *p = L;
    if (!p)
        return false;
    while (p != NULL)
    {
        printf("%d->", p->data);
        p = p->next;
    }
    printf("NULL\n");
    return true;
}

// 逆置 --- 头插法
void HeadInsertReverse(LinkedList &L)
{
    LNode *p = NULL;
    LNode *head = L->next;
    while (head != NULL)
    {
        LNode *next = head->next;
        head->next = p;
        p = head;
        head = next;
    }
    L->next = p;
}

// 逆置 --- 递归
void RecursionReverse()
{
}

// 查找中间节点
LNode *GetMidNode(LinkedList L)
{
    LNode *slow = L;
    LNode *fast = L;
    while (fast != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// int main()
// {
//     // 初始化
//     LinkedList L;
//     InitList(L);

//     // 插入
//     ListInsert(L, 1, 2);
//     ListInsert(L, 2, 5);
//     ListInsert(L, 3, 9);
//     ListInsert(L, 4, 7);
//     ListInsert(L, 5, 3);
//     ListInsert(L, 6, 6);
//     PrintList(L);

//     // 查看中间节点
//     LNode *mid = GetMidNode(L);
//     printf("中间节点值为%d", mid->data);

//     // 反转
//     printf("头插法反转链表\n");
//     HeadInsertReverse(L);
//     PrintList(L);

//     // 删除
//     int e;
//     ListDelete(L, 3, e);
//     printf("删除了元素: %d\n", e);
//     PrintList(L);

//     // 清空
//     ClearList(L);
//     return 0;
// }